home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / triang.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  2KB  |  142 lines
  1. #include <LEDA/plane.h>
  2. #include <LEDA/d_array.h>
  3. #include <LEDA/graph.h>
  4. #include <LEDA/window.h>
  5.  
  6. window W;
  7.  
  8. void TRIANG(list<point> L, GRAPH<point,int>& G)
  9. { 
  10.   if (L.length() < 3) return;
  11.  
  12.   list<point> CH;
  13.   list_item last;
  14.  
  15.   L.sort();  // sort points lexicographically
  16.  
  17.   d_array<point,node> V(nil);
  18.  
  19.  
  20.  
  21.   // initialize convex hull with first two points
  22.  
  23.   point p = L.pop();
  24.   V[p] = G.new_node(p);
  25.   CH.append(p);
  26.  
  27.   while (L.head() == p) L.pop();
  28.   point q = L.pop();
  29.   last = CH.append(q);
  30.   V[q] = G.new_node(q);
  31.  
  32.   G.new_edge(V[p],V[q]);
  33.  
  34.  
  35.   // scan remaining points
  36.  
  37.   forall(p,L)
  38.   {
  39.     if (p == CH[last]) continue;  // multiple point
  40.  
  41.     node v = G.new_node(p);
  42.  
  43.     V[p] = v;
  44.  
  45.     G.new_edge(v,V[CH[last]]);
  46.  
  47.     // compute upper tangent (p,up)
  48.  
  49.     list_item up = last;
  50.     list_item it = CH.cyclic_succ(up);
  51.  
  52.     while (left_turn(CH[it],CH[up],p))
  53.     { up = it;
  54.       it = CH.cyclic_succ(up);
  55.       G.new_edge(v,V[CH[up]]);
  56.      }
  57.  
  58.  
  59.     // compute lower tangent (p,low)
  60.  
  61.     list_item low = last;
  62.     it = CH.cyclic_pred(low);
  63.  
  64.     while (right_turn(CH[it],CH[low],p))
  65.     { low = it;
  66.       it = CH.cyclic_pred(low);
  67.       G.new_edge(v,V[CH[low]]);
  68.      }
  69.  
  70.  
  71.     // remove all points between up and low
  72.  
  73.     if (up != low)
  74.     { it = CH.cyclic_succ(low);
  75.  
  76.       while (it != up)
  77.       { CH.del(it);
  78.         it = CH.cyclic_succ(low);
  79.        }
  80.      }
  81.  
  82.     // insert new point
  83.  
  84.     last = CH.insert(p,low);
  85.  
  86.    }
  87.  
  88. }
  89.      
  90.  
  91.  
  92. main()
  93. {
  94.   //window W;
  95.   W.init(-100,100,-100);
  96.   W.set_node_width(5);
  97.  
  98.   int N = 500;
  99.  
  100.   panel P("triangulation");
  101.  
  102.   P.int_item("# points",N,1,2000);
  103.   int b1 = P.button("mouse");
  104.   int b2 = P.button("random");
  105.   int b3 = P.button("quit");
  106.  
  107.   for(;;)
  108.   { 
  109.     list<point> L;
  110.     point p,q;
  111.  
  112.     int but = P.open();
  113.  
  114.     W.clear();
  115.  
  116.     if (but == b1)
  117.       while (W >> p)
  118.       { W.draw_point(p,blue);
  119.         L.append(p);
  120.        }
  121.  
  122.     if (but == b2)
  123.       for(int i = 0; i<N; i++) 
  124.       { point p(random(-90,90),random(-90,90));
  125.         W.draw_point(p,blue);
  126.         L.append(p);
  127.        }
  128.  
  129.     if (but == b3) break;
  130.   
  131.     GRAPH<point,int> G;
  132.     TRIANG(L,G);
  133.   
  134.     edge e;
  135.     forall_edges(e,G)
  136.        W.draw_segment(G[source(e)],G[target(e)],violet);
  137.   }
  138.    
  139.  return 0;
  140. }
  141.  
  142.